/**
 * 项目排期，求把m个任务分给n个同事，最短能全部完成的事件T
 * 实际上会转换成要把m个球(任务)放到n个桶（同事）里，要求每个桶里的球要最少Math.min(Math.max(桶[1],桶[2]...桶[n]))
 * 这m个球不是1个个打散的，而是被拆分在一些球包中，每个球包里都有随机数量的球，所有球的数量是m。
 * @param {*} balls 记录球包的数组，所有球的总数为m
 * @param {*} n 桶的数量，或者按项目排期的题目来说，就是员工的数量
 * @returns
 */
function getResult(balls, n) {
    // 这里对balls降序，有利于降低后面回溯操作的复杂度
    balls.sort((a, b) => b - a);

    // 二分范围：即每个桶的容量最小，最大值
    let min = balls[0]; // 桶至少要有max(balls)的容量
    let max = balls.reduce((a, b) => a + b); // 当只有一个桶时，此时该桶容量要装下所有balls球
    console.log(`[getResult] min: ${min},max: ${max}`);

    // 记录题解
    let ans = max;

    // 二分找中间值作为桶容量
    while (min <= max) {
        const mid = (min + max) >> 1;
        console.log(`[MID] mid:${mid}`);
        if (check(balls, 0, new Array(n).fill(0), mid)) {
            // 如果k个mid容量的桶，可以装完所有balls球，那么mid容量就是一个可能解，但不一定是最优解，我们应该尝试更小的桶容量
            ans = mid;
            max = mid - 1;
        } else {
            // 如果k个mid容量的桶，无法装完所有balls球，那么说明桶容量取小了，我们应该尝试更大的桶容量
            min = mid + 1;
        }
    }

    return ans;
}

/**
 * @param {*} balls 球数组，记录了每个球包中球的数量
 * @param {*} index 当前轮次将要被装入的球（balls）索引
 * @param {*} buckets 桶数组，buckets[i]记录第i个桶的已使用的容量
 * @param {*} limit 每个桶的最大容量，即限制
 * @returns k个桶（每个桶容量limit）是否可以装下balls中所有球
 */
function check(balls, index, buckets, limit) {
    console.log(
        `[check] 
        index:${index}, 
        buckets:${JSON.stringify(buckets)}, 
        limit:${limit}`
    );

    // 回溯，递归出口，因为能递归到balls.length证明所有球都分配完毕了
    // 如果所有球已经取完，则说明k个limit容量的桶，可以装完所有balls球
    if (index == balls.length) return true;

    // select是当前要装的球
    const selected = balls[index];

    // 遍历桶
    for (let i = 0; i < buckets.length; i++) {
        // 剪枝优化
        if (i > 0 && buckets[i] == buckets[i - 1]) continue;

        // 如果当前桶装了当前选择的球后不超过容量限制，则可以装入
        if (selected + buckets[i] <= limit) {
            buckets[i] += selected;
            // 递归装下一个球
            if (check(balls, index + 1, buckets, limit)) {
                return true;
            }
            // 如果这种策略无法装完所有球，则回溯
            // 换下一个桶装这个球
            buckets[i] -= selected;
        }
    }

    return false;
}

// test
let arr = [6, 2, 7, 7, 9, 3, 2, 1, 3, 11, 4];
let n = 2;
let res = getResult(arr, n);

console.log(res);
